package Union;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class unionFind {

    //样本进来会包一层,叫做元素
    public static class Element<V>{
        public V value;
        public Element(V value){
            this.value = value;
        }
    }
    public static class UnionFindSet<V>{
        //这个类,就是将原来单链表的图,拆成俩个哈希表来记录
        public HashMap<V,Element<V>> elementMap;
        //key 某个元素, value该元素的父亲,给一个值一一对应的元素
        public HashMap<Element<V>,Element<V>> fatherMap;
        //key是某个集合的代表元素,value是该集合的大小
        public HashMap<Element<V>,Integer> sizeMap;
        //留代表该集合的元素

        public UnionFindSet(List<V> list){
            //在初始化的时候,要求用户把样本都给你
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : list){
                Element<V> element = new Element<>(value);
                elementMap.put(value,element);
                fatherMap.put(element,element);
                //任何一个元素各自成圈,大小都是1
                sizeMap.put(element,1);
            }
        }
        private Element<V> findHead(Element<V> element){
            //给定一个值,一直往上找
            Stack<Element<V>> path = new Stack<>();

            while (element != fatherMap.get(element)){
                path.push(element);
                element = fatherMap.get(element);
            }
            //找到后,将该链表的每个元素的父节点都改成element
            while (! path.isEmpty()){
                fatherMap.put(path.pop(),element);
            }
            return element;
        }

        public boolean isSameSet(V a,V b){
            if (elementMap.containsKey(a)){
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }
        public void union(V a, V b){
            //俩个元素检查是否注册过
            if (elementMap.containsKey(a) && elementMap.containsKey(b)){
                Element<V>  aF = findHead(elementMap.get(a));
                Element<V>  bF = findHead(elementMap.get(b));
                if (aF != bF){
                    //如果俩个头结点不相等,找到链表值多的那一个
                    Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF)? aF : bF;
                    Element<V> small = big == aF ?bF:aF;
                    //将链表值小的那个一个的顶端挂到数量多的的顶端上
                    fatherMap.put(small,big);
                    //改变size和移除size
                    sizeMap.put(big,sizeMap.get(aF)+sizeMap.get(bF));
                    sizeMap.remove(small);
                }
            }
        }
    }
}
